Transformation is an essential component of image and video coding. A substantial number of compression standards utilize a Discrete Cosine Transform (DCT), which is an image-independent transform. DCT includes an algorithm, similar to Fast Fourier Transform, which converts data (pixels, waveforms, etc.) into sets of frequencies, whereby, for compression purposes, latter frequencies are stripped away based on allowable resolution loss. For video compression in devices with weak computational power including some portable devices, the high complexity of DCT is not conducive to robust processing. Therefore, alternatives for DCT are being pursued, having low computational complexity and high compression efficiency.
The pursuit of alternatives to DCT focuses on simplified transforms. Examples of such approaches to such simplified transforms include (1) a factorization-based approach and (2) an integer transform kernel redesign approach.
A factorization-based approach operates similarly to most fast algorithms for DCT, which factorize DCT to the multiple of a Walsh matrix and some sparse matrices, and then approximate the floating-point coefficients of the latter by integer or binary fractions. Examples of this approach include the C-matrix transform (CT) (Jones, et al., The Karhunen-Loeve Discrete Cosine and Related Transforms Obtained via the Hadamard Transform, Proc. Intl. Telemetering Conference, Los Angeles, Nov. 14, 1978, pp. 87-98) and the recently popular Integer DCT (IntDCT) with lifting scheme (Chen, et al., Integer Discrete Cosine Transform (IntDCT), IEEE Trans. Signal Processing, February 2000, pp. 1-5). CT and IntDCT closely resemble DCT and are able to provide high compression. However, CT and IntDCT divide the original transform into several steps, particularly a Walsh-Hadamard transform and some sparse matrices. Although sparse matrices can be computed by fast algorithms, the total complexity is always a multiple of WHT, which is not easily reduced.
The integer transform kernel redesign approach directly designs a simple matrix to replace the floating-point DCT. This approach provides much freedom except for a matrix orthogonality restraint. The challenge of this approach is that maintaining high compression efficiency has proven to be a difficult task.
A first method in the integer transform kernel redesign approach starts with scaling the original DCT by a large integer and then searching for integer coefficients with respect to orthogonality restrictions (G. Bjontegaard, Addition of 8×8 Transform to H.26L, ITU-T Q15/SG16, Document Q15-I-39, Red Bank, N.J., October 2000; and Wien, et al., Integer Transforms for H. 26L using Adaptive Block Transforms, ITU-T Q15/SG16, Document Q15-K-24, Portland, Oreg., August 2000). A drawback of this method is that the elements of the matrix elements are often large integers, thus increasing computational complexity.
A second method in the integer transform kernel redesign approach designs a new symmetric and orthogonal matrix template and then produces a transform family. Representative results of the second method are Cham's integer cosine transform (ICT) (Cham, Development of integer cosine transforms by the principle of dyadic symmetry, IEEE Proceedings, Vol. 136, Pt. 1, No. 4, August 1989) and the dyadic transform (DT) (Lo, et al., Development of simple orthogonal transforms for image compression, IEEE Proc.-Vis. Image Signal Process., Vol. 142, No. 1, February 1995) family. These transforms can provide low complexity but with unsatisfactory compression efficiency. The matrix of DT implements an 8-point transform with only 28 additions plus 10 binary shifts, but it is completely incompatible with DCT. ICT's representative (5, 3, 2, 1) is more complex than DT, but the compression efficiency of ICT is listed between that of IntDCT and CT.